package U5;

import java.awt.HeadlessException;
import java.util.*;

public class Test3 {
	public class TreeNode {
		int val = 0;
		TreeNode left = null;
		TreeNode right = null;
	}
	public ArrayList<Integer> inorderTraversal(TreeNode root) {
		// write code here
		List<Integer> res = new ArrayList<Integer>();
		if(root != null) {
			Stack<TreeNode> stack = new Stack<TreeNode>();
			while(!stack.isEmpty() || root != null) {
				if(root != null) {
					stack.push(root);
					root = root.left;
				}else {
					root = stack.pop();
					res.add(root.val);
					root = root.right;
				}
				
			}
		}
		return  (ArrayList<Integer>) res;
	}
	
	public ArrayList<Integer> inorderTraversal1(TreeNode root) {
		// write code here
		List<Integer> res = new ArrayList<Integer>();
		dfs(root,res);
		return  (ArrayList<Integer>) res;
		
	}

	private void dfs(TreeNode root, List<Integer> res) {
		if(root == null) return;
        if(root.left != null) dfs(root.left,res);
        res.add(root.val);
        if(root.right != null) dfs(root.right,res);
		
	}

}
